/**
 * N 皇后 2
 *
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
 *
 * 示例 1：
 * 输入：n = 4
 * 输出：2
 * 解释：如上图所示，4 皇后问题存在两个不同的解法。
 *
 * 示例 2：
 * 输入：n = 1
 * 输出：1
 *
 * 提示：
 * 1 <= n <= 9
 */

/**
 * 这题和上一题 51.N 皇后 一样
 * 时间复杂度 : O(n! * n)
 * 空间复杂度 : O(n^2)
 */

public class Main {
    // 定义全局变量
    int n;

    // 这里用 int 来表示格子状态, == 0 表示不会被攻击, > 0 表示会被攻击
    int[][] tmp;

    // 记录有多少种放法
    int ret = 0;

    public int totalNQueens(int len) {
        n = len;
        tmp = new int[n][n];
        dfs(0);
        return ret;
    }

    /**
     * 深搜
     *
     * @param k : 用来标识正在处理多少层
     */
    private void dfs (int k) {

        // 要是遍历到 第 n 层 说明已经遍历完, 出口
        if (k == n) {
            ret++;
            return;
        }

        // 同一层中有 n 个数
        for (int i = 0; i < n; i++) {

            // 要是这格的状态为不会被攻击就加入
            if (tmp[k][i] == 0) {

                // 扭转相关联的状态, 就是关联格子 +1
                changeStatus(k, i, 1);

                // 深搜下一层
                dfs (k + 1);

                // 恢复现场

                // 在恢复状态的时候有个小细节, 我们之所以不用 boolean 来表示格子状态
                // 就是因为在恢复现场时, 要是 boolean 类型会让之前别的格子改变的状态
                // 一起改回不回受攻击, 所以我们用 int , 在恢复的时候进行关联格子 -1
                changeStatus(k, i, -1);
            }
        }
    }

    /**
     * 扭转相应的状态
     *
     * @param a
     * @param b
     * @param vaild
     */
    private void changeStatus(int a, int b, int vaild) {

        for (int i = 0; i < n; i++) {

            // 更改 |
            tmp[i][b] += vaild;

            // 更改 --
            tmp[a][i] += vaild;
        }

        for (int i = 0; i < n; i++) {

            // 更改 /
            if (a - i >= 0 && b + i < n) {
                tmp[a - i][b + i] += vaild;
            }
            if (b - i >= 0 && a + i < n) {
                tmp[a + i][b - i] += vaild;
            }

            // 更改 \
            if (a - i >= 0 && b - i >= 0) {
                tmp[a - i][b - i] += vaild;
            }
            if (a + i < n && b + i < n) {
                tmp[a + i][b + i] += vaild;
            }
        }
    }

    // 测试用例
    public static void main(String[] args) {
        Main test = new Main();
        System.out.println(test.totalNQueens(4));
    }
}